#include "LinkList2.h"
#include <iostream>


LinkList::LinkList():size(0)
{
    head = new Node(0); //头结点
}

LinkList::LinkList(const LinkList& list) //拷贝构造
{
    size = 0;
    head = new Node(0);
    Node *Tp = list.head->next;
    while(Tp != nullptr)
    {
        InsertTail(Tp->value);
        Tp = Tp->next;
    }
}

LinkList::~LinkList()
{
    while(head != nullptr)
    {
        Node * nextNode = head->next;
        delete head;
        head = nextNode;
    }
}

void LinkList::show()
{
    Node *TravelPoint = head->next;
    while(TravelPoint != nullptr)
    {
        std::cout<<TravelPoint->value<<" ";
        TravelPoint = TravelPoint->next;
    }
    std::cout<<std::endl;
}

void LinkList::InsertTail(const ElementType& element)
{
    Node * TravelPoint = head; //遍历指针
    while(TravelPoint->next != nullptr) //找末尾
    {
        TravelPoint = TravelPoint->next;
    }
    TravelPoint->next = new Node(element);
    size++;
}

void LinkList::InsertHead(const ElementType& element)
{
    Node * newNode = new Node(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
}

void LinkList::InsertByIndex(int index,const ElementType &element)
{
    if(index < 0 || index > size)
    {
        return;
    }
    Node *trevalPoint = head;
    for(int i = 0; i < index; i++)//取到要插入节点的前一位置
    {
        trevalPoint = trevalPoint->next;
    }
    Node *nextNode = new Node(element);
    nextNode->next = head->next;
    head->next = nextNode;
    size++;
}

void LinkList::RemvoeByIndex(int index)
{
    if(index < 0 || index >= size)
    {
        return;
    }
    Node *trevalPoint = head;
    for(int i = 0; i < index; i++)
    {
        trevalPoint = trevalPoint->next;
    }
    Node *FreeNode = trevalPoint->next;
    trevalPoint->next = FreeNode->next;
    // trevalPoint->next = trevalPoint->next->next;
    delete FreeNode;
    size--;
}

void LinkList::RemoveByElement(const ElementType& element)
{
    Node *Tp = head;
    while(Tp->next != nullptr)
    {
        if(Tp->next->value == element)
        {
            Node *FreeNode = Tp->next;
            Tp->next = FreeNode->next;
            delete FreeNode;
            size--;
        }
        else
        {
            Tp = Tp->next;
        }
    }
}

void LinkList::UpdateByIndex(int index,const ElementType& element)
{
    if(index < 0 || index >= size)
    {
        return;
    }
    Node *Tp = head;
    for(int i = 0; i <= index; i++) //直接修改要找的那个下标，不用通过前一个的指针进行操作
    {
        Tp = Tp->next;
    }
    Tp->value = element;
}

void LinkList::UpdateByElement(const ElementType& Oldvalue,const ElementType& Newvalue)
{
    Node *Tp = head->next;
    while(Tp->next != nullptr)
    {
        if(Tp->value == Oldvalue)
        {
            Tp->value = Newvalue;
        }
        Tp = Tp->next;
    }
}

void LinkList::BubbleSort()
{
    for(int i = 0; i < size - 1; i++)
    {
        Node *Tp = head;
        for(int j =0; j < size - i - 1; j++)
        {
            if( Tp->next->value > Tp->next->next->value)
            {
                Node *preNode = Tp->next;
                Node *nextNode = preNode->next;
                Tp->next = nextNode;
                preNode->next = nextNode->next;
                nextNode->next = preNode;
            }
            Tp = Tp->next;
        }
    }
}


LinkList LinkList::Merge(const LinkList& list)
{
    LinkList result;
    Node *p1 = head->next;
    Node *p2 = list.head->next;
    while(p1 && p2)
    {
        if(p1->value > p2->value)
        {
            result.InsertTail(p2->value);
            p2 = p2->next;
        }
        else
        {
            result.InsertTail(p1->value);
            p1 = p1->next;
        }
    }
    while(p1)
    {
        result.InsertTail(p2->value);
        p1 = p1->next;
    }
    while(p2)
    {
        result.InsertTail(p2->value);
        p2 = p2->next;
    }
    return result;
}

void LinkList::Sort()
{
    FastSort(head->next,nullptr);
}

void LinkList::FastSort(Node * start,Node * end)
{
   if(start == end)
   {
        return;
   }
   Node *temp = start;
   Node *slow = start;
   Node *fast = start->next;
   while(fast != end)
   {
        if(fast->value < temp->value)
        {
            slow = slow->next;
            std::swap(fast->value,slow->value);
        }
        fast = fast->next;
   }
   std::swap(temp->value,slow->value);
   FastSort(start,slow);
   FastSort(slow->next,end);
}

void LinkList::Reserve()
{
    Node *prev = nullptr;
    Node *cur = head->next;
    Node *Next = cur->next;
    while(Next != nullptr)
    {
        cur->next = prev;
        prev = cur;
        cur = Next;
        Next = cur->next;
    }
    cur->next = prev;
    head->next = cur;
}

void LinkList::Reserve2()
{
    head->next = Reserve2(head->next);
}

LinkList::Node * LinkList::Reserve2(Node * node)
{
    if(node->next == nullptr)
    {
        return node;
    }
    else
    {
        Node *newHead = Reserve2(node->next);
        node->next->next = node;
        node->next = nullptr;
        return newHead;
    }
}

